{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Wiggle Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wiggleMaxLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #摆动序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为<strong> 摆动序列 。</strong>第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>\n",
    "\t<p>例如， <code>[1, 7, 4, 9, 2, 5]</code> 是一个 <strong>摆动序列</strong> ，因为差值 <code>(6, -3, 5, -7, 3)</code> 是正负交替出现的。</p>\n",
    "\t</li>\n",
    "\t<li>相反，<code>[1, 4, 7, 2, 5]</code> 和 <code>[1, 7, 4, 5, 5]</code> 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>子序列</strong> 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>nums</code> ，返回 <code>nums</code> 中作为 <strong>摆动序列 </strong>的 <strong>最长子序列的长度</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,7,4,9,2,5]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,17,5,10,13,15,10,5,16,8]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>这个序列包含几个长度为 7 摆动序列。\n",
    "其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4,5,6,7,8,9]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 1000</code></li>\n",
    "\t<li><code>0 <= nums[i] <= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能否用 <code>O(n)</code><em> </em>时间复杂度完成此题?</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [wiggle-subsequence](https://leetcode.cn/problems/wiggle-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [wiggle-subsequence](https://leetcode.cn/problems/wiggle-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,7,4,9,2,5]', '[1,17,5,10,13,15,10,5,16,8]', '[1,2,3,4,5,6,7,8,9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        sz1 = len(nums)\n",
    "        if sz1 <= 1:\n",
    "            return sz1\n",
    "        \n",
    "        sz2 = sz1 - 1\n",
    "        A = [0 for i in range(sz2)]\n",
    "        \n",
    "        for i in range(sz2):\n",
    "            a = nums[i]\n",
    "            b = nums[i + 1]\n",
    "            A[i] = b - a\n",
    "        \n",
    "        # print(A)\n",
    "        \n",
    "        B = [0 if A[i] == 0 else 1 for i in range(sz2)]\n",
    "        \n",
    "        for j in range(1, sz2):\n",
    "            b = A[j]\n",
    "            for i in range(j):\n",
    "                a = A[i]\n",
    "                if (a > 0 and b < 0) or (a < 0 and b > 0):\n",
    "                    B[j] = max(B[j], B[i] + 1)\n",
    "        \n",
    "        return max(B) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        # O(n^2)\n",
    "        # n = len(nums)\n",
    "        # if n < 2:\n",
    "        #     return n\n",
    "        # len_p = [1] * n\n",
    "        # len_n = [1] * n\n",
    "        # for i in range(1, n):\n",
    "        #     for j in range(0, i):\n",
    "        #         if nums[i] > nums[j]:\n",
    "        #             len_p[i] = max(len_p[i], len_n[j] + 1)\n",
    "        #         elif nums[i] < nums[j]:\n",
    "        #             len_n[i] = max(len_n[i], len_p[j] + 1)\n",
    "        # return max(len_p + len_n)\n",
    "    \n",
    "        # O(n)\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return n\n",
    "        max_len = 1\n",
    "        sign = 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                if max_len == 1 or sign == -1:\n",
    "                    max_len += 1\n",
    "                sign = 1\n",
    "            elif nums[i] < nums[i - 1]:\n",
    "                if max_len == 1 or sign == 1:\n",
    "                    max_len += 1\n",
    "                sign = -1\n",
    "            # else:\n",
    "                # sign = 0  this is not correct? keep the last sign.\n",
    "                \n",
    "#             d1 = 0\n",
    "#         count = 1\n",
    "#         for i in range(1, len(nums)):\n",
    "#             d2 = nums[i] - nums[i-1]\n",
    "#             if d2 == 0:\n",
    "#                 continue\n",
    "                \n",
    "#             if d1 * d2 <= 0:\n",
    "#                 count += 1\n",
    "#                 d1 = d2    \n",
    "        return max_len\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return 0\n",
    "        counti = countd = 1\n",
    "        lasti1 = lastd1 = nums[0]\n",
    "        flagi, flagd, lasti0, lastd0 = 1, -1, lasti1 + 1, lastd1 - 1\n",
    "        for num in nums[1:]:\n",
    "            if flagi == 1:\n",
    "                if num > lasti1:\n",
    "                    counti += 1\n",
    "                    lasti0, lasti1, flagi = lasti1, num, -flagi\n",
    "                elif num < lasti0:\n",
    "                    lasti1 = num\n",
    "            else:\n",
    "                if num < lasti1:\n",
    "                    counti += 1\n",
    "                    lasti0, lasti1, flagi = lasti1, num, -flagi\n",
    "                elif num > lasti0:\n",
    "                    lasti1 = num\n",
    "            if flagd == -1:\n",
    "                if num < lastd1:\n",
    "                    countd += 1\n",
    "                    lastd0, lastd1, flagd = lastd1, num, -flagd\n",
    "                elif num > lastd0:\n",
    "                    lastd1 = num\n",
    "            else:\n",
    "                if num > lastd1:\n",
    "                    countd += 1\n",
    "                    lastd0, lastd1, flagd = lastd1, num, -flagd\n",
    "                elif num < lastd0:\n",
    "                    lastd1 = num\n",
    "        return max(counti, countd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums):\n",
    "        wig_len = 1 # 摇摆数列最少一个元素\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return n\n",
    "        up = 1\n",
    "        down = 1\n",
    "        for i in range(1,n):\n",
    "\n",
    "            if nums[i] > nums[i-1]:\n",
    "                up = down + 1  # 序列一直增，但down没有更新，所以up并不增\n",
    "\n",
    "            elif nums[i] < nums[i-1]:\n",
    "                down = up + 1\n",
    "\n",
    "\n",
    "        return  max(up, down)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        up, down = 1, 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                up = down + 1\n",
    "            elif nums[i] < nums[i - 1]:\n",
    "                down = up + 1\n",
    "        return max(up, down)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if(n < 2): return n\n",
    "        prev, res = 0, 1\n",
    "        for i in range(1, n):\n",
    "            if(nums[i] == nums[i-1]):\n",
    "                continue\n",
    "            if(nums[i] > nums[i-1]):\n",
    "                curr = 1\n",
    "            else:\n",
    "                curr = -1\n",
    "            if(prev != curr):# 看变化趋势，去掉所有 非 波峰波谷的点\n",
    "                res += 1\n",
    "            prev = curr\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        ans=1\n",
    "        temp=nums[0]\n",
    "        sign=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]>temp:\n",
    "                if sign!=1:\n",
    "                    sign=1\n",
    "                    ans+=1\n",
    "                temp=nums[i]\n",
    "            elif nums[i]<temp:\n",
    "                if sign!=-1:\n",
    "                    sign=-1\n",
    "                    ans+=1\n",
    "                temp=nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2: return len(nums)\n",
    "        max_len = 1\n",
    "        state = 'begin'\n",
    "        for i in range(1,len(nums)):\n",
    "            if state == 'begin':\n",
    "                if nums[i-1] == nums[i]:\n",
    "                    continue\n",
    "                elif nums[i-1] < nums[i]:\n",
    "                    state = 'up'\n",
    "                    max_len += 1\n",
    "                else:\n",
    "                    state = 'down'\n",
    "                    max_len +=1\n",
    "            elif state == 'up':\n",
    "                if nums[i] >= nums[i-1]:\n",
    "                    continue\n",
    "                else:\n",
    "                    state = 'down'\n",
    "                    max_len += 1\n",
    "            elif state == 'down':\n",
    "                if nums[i] <= nums[i-1]:\n",
    "                    continue\n",
    "                else:\n",
    "                    state = 'up'\n",
    "                    max_len += 1\n",
    "        return max_len\n",
    "           \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        if len(nums)<2:\n",
    "            return len(nums)\n",
    "    \n",
    "        for i in range(len(nums)-1):\n",
    "            if (nums[i]-nums[i+1])>0:\n",
    "                flag=1\n",
    "                break\n",
    "            elif (nums[i]-nums[i+1])<0:\n",
    "                flag=0\n",
    "                break\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "        if i+1==(len(nums)-1):\n",
    "            return 1\n",
    "        ans=1\n",
    "        for j in range(i+1,len(nums)-1):\n",
    "            if (nums[j]-nums[j+1])==0:\n",
    "                continue\n",
    "            temp_flag=0 if (nums[j]-nums[j+1])<0 else 1\n",
    "            if temp_flag==flag:\n",
    "                continue\n",
    "            else:\n",
    "                flag=temp_flag\n",
    "                ans+=1\n",
    "        return (ans+1)\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 1:\n",
    "            return len(nums)\n",
    "        dp0, dp1 = 1, 1\n",
    "        flag = -(nums[1]-nums[0])\n",
    "        for i in range(1, len(nums)):\n",
    "            if flag >= 0 and nums[i] - nums[i-1] < 0:\n",
    "                flag = nums[i] - nums[i-1]\n",
    "                dp1 = dp0 + 1\n",
    "            elif flag <= 0 and nums[i] - nums[i-1] > 0:\n",
    "                flag = nums[i] - nums[i-1]\n",
    "                dp1 = dp0 + 1\n",
    "            else:\n",
    "                dp1 = dp0\n",
    "            dp0 = dp1\n",
    "        return dp1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return n\n",
    "        \n",
    "        up = down = 1\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                up = down + 1\n",
    "            elif nums[i] < nums[i - 1]:\n",
    "                down = up + 1\n",
    "        \n",
    "        return max(up, down)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums) -> int:\n",
    "        if len(nums) <= 1:\n",
    "            return len(nums)\n",
    "        if len(nums) == 2:\n",
    "            if nums[0] != nums[1]:\n",
    "                return 2\n",
    "            else:\n",
    "                return 1\n",
    "\n",
    "        up = 1\n",
    "        down = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] - nums[i-1] > 0:\n",
    "                up = down + 1\n",
    "            if nums[i] - nums[i-1] < 0:\n",
    "                down = up + 1\n",
    "        return max(up, down)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        # if not nums:\n",
    "        #     return 0\n",
    "        # dp = [[1, 1] for _ in range(len(nums))]\n",
    "        # for i in range(1, len(nums)):\n",
    "        #     for j in range(i):\n",
    "        #         if nums[i] > nums[j]:\n",
    "        #             dp[i][1] = max(dp[i][1], dp[j][0] + 1)\n",
    "        #         elif nums[i] < nums[j]:\n",
    "        #             dp[i][0] = max(dp[i][0], dp[j][1] + 1)\n",
    "        # return max(map(max, dp))\n",
    "\n",
    "        if not nums:\n",
    "            return 0\n",
    "        dp = [[1, 1] for _ in range(len(nums))]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i][0] = max([dp[j][1] + 1 for j in range(i) if nums[j] > nums[i]] + [dp[i][0]])\n",
    "            dp[i][1] = max([dp[j][0] + 1 for j in range(i) if nums[j] < nums[i]] + [dp[i][1]])\n",
    "        return max(map(max, dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def handle(idx: int, flag: int) -> int:\n",
    "            if idx == 0:\n",
    "                return 1\n",
    "            ans = 1\n",
    "            for i in range(idx):\n",
    "                if flag * nums[idx] < flag * nums[i]:\n",
    "                    ans = max(ans, handle(i, -1 * flag) + 1)\n",
    "            \n",
    "            return ans\n",
    "        \n",
    "        return max(handle(len(nums) - 1, 1), handle(len(nums) - 1, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2:\n",
    "            return len(nums)\n",
    "\n",
    "        if len(nums) < 3:\n",
    "            if nums[0] != nums[1]:\n",
    "                return 2\n",
    "            else:\n",
    "                return 1\n",
    "            return len(nums)\n",
    "        ans = []\n",
    "        dp = [[x] for x in nums]\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(i):\n",
    "                if len(dp[j]) < 2:\n",
    "                    if dp[j][0] != nums[i]:\n",
    "                        dp[i] = dp[j] + [nums[i]]\n",
    "                    \n",
    "                else:\n",
    "                    if (dp[j][-2] -dp[j][-1])*(dp[j][-1] - nums[i]) < 0:\n",
    "                        dp[i] = dp[j] + [nums[i]]\n",
    "                if len(ans) < len(dp[i]):\n",
    "                    ans = dp[i]\n",
    "            \n",
    "        return len(ans)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        if len(nums)<=1:\n",
    "            return len(nums)\n",
    "        curdiff=0\n",
    "        prediff=0\n",
    "        result=1 #记录峰值个数，序列默认最右边有1个峰值\n",
    "        for i in range(1,len(nums)):\n",
    "            curdiff=nums[i]-nums[i-1]\n",
    "            if (curdiff>0 and prediff<=0) or (curdiff<0 and prediff>=0):\n",
    "                result+=1\n",
    "                prediff=curdiff\n",
    "\n",
    "        return result \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        if len(nums) == 1:\n",
    "            return 1\n",
    "        else:\n",
    "            prediff = 0\n",
    "            curdiff = 0\n",
    "            result = 1\n",
    "            for i in range(len(nums)-1):\n",
    "                curdiff = nums[i+1] - nums[i]\n",
    "\n",
    "                if (prediff >= 0 and curdiff < 0) or (prediff <= 0 and curdiff > 0):\n",
    "                    result += 1\n",
    "                    prediff = curdiff\n",
    "                \n",
    "            return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        cnt = 1\n",
    "        tail = nums[0]\n",
    "        sign = None\n",
    "        for i in range(1, len(nums)):\n",
    "            diff = nums[i] - tail\n",
    "            if sign is None:\n",
    "                if diff == 0:\n",
    "                    continue\n",
    "                tail = nums[i]\n",
    "                sign = 1 if diff > 0 else -1\n",
    "                cnt += 1\n",
    "            else:\n",
    "                if sign * diff < 0:\n",
    "                    tail = nums[i]\n",
    "                    sign = -1 * sign\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    if sign > 0:\n",
    "                        tail = max(tail, nums[i])\n",
    "                    else:\n",
    "                        tail = min(tail, nums[i])\n",
    "        return cnt\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1: return 1\n",
    "        res = 1\n",
    "        cur_diff = 0\n",
    "        pre_diff = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            cur_diff = nums[i+1] - nums[i]\n",
    "            if (cur_diff > 0 and pre_diff <= 0) or (cur_diff < 0 and pre_diff >= 0 ):\n",
    "                res += 1\n",
    "                pre_diff = cur_diff\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        size = len(nums)\n",
    "        dp = [[1,1] for _ in range(size)]\n",
    "        max_l = 1\n",
    "        for i in range(1,size):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "            else:\n",
    "                preminus = [dp[k][1] for k in range(i) if nums[k] < nums[i]]\n",
    "                preplus = [dp[k][0] for k in range(i) if nums[k] > nums[i]]\n",
    "                if preminus == []:\n",
    "                    dp[i][0] = 1\n",
    "                else:\n",
    "                    dp[i][0] = max(preminus) + 1\n",
    "\n",
    "                if preplus == []:\n",
    "                    dp[i][1] = 1\n",
    "                else:\n",
    "                    dp[i][1] = max(preplus) + 1\n",
    "                max_l = max(max_l, dp[i][0], dp[i][1])\n",
    "        return max_l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        m = len(nums) \n",
    "\n",
    "        @cache \n",
    "        def dfs(i, j):\n",
    "            if i == 0:\n",
    "                return 1 \n",
    "            res = -inf \n",
    "            for k in range(i):\n",
    "                if j == 1 and nums[k] < nums[i]:\n",
    "                    res = max(res, dfs(k, 0) + 1) \n",
    "                if j == 0 and nums[k] > nums[i]:\n",
    "                    res = max(res, dfs(k, 1) + 1) \n",
    "            return res \n",
    "        \n",
    "        return max(dfs(m-1, 1), dfs(m-1, 0), 1) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 1\n",
    "        pred = 0\n",
    "        curd = 1\n",
    "        res = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            curd = nums[i] - nums[i - 1]\n",
    "            if pred >= 0 and curd < 0:\n",
    "                res += 1\n",
    "                pred = curd\n",
    "            if pred <= 0 and curd > 0:\n",
    "                res += 1\n",
    "                pred = curd\n",
    "            \n",
    "        return res    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 1: return len(nums)\n",
    "        prediff = 0\n",
    "        #curdiff = 0\n",
    "        res = 1\n",
    "        for i in range(len(nums)-1):\n",
    "            curdiff = nums[i+1] - nums[i]\n",
    "            if (prediff >= 0 and curdiff < 0) or (prediff <= 0 and curdiff > 0):\n",
    "                res += 1\n",
    "                prediff = curdiff\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleMaxLength(self, nums: List[int]) -> int:\n",
    "        dp = []\n",
    "        for i in range(len(nums)):\n",
    "            dp.append([1, 1])\n",
    "            for j in range(i):\n",
    "                if nums[j] > nums[i]:\n",
    "                    dp[i][1] = max(dp[i][1], dp[j][0] + 1)\n",
    "                if nums[j] < nums[i]:\n",
    "                    dp[i][0] = max(dp[i][0], dp[j][1] + 1)\n",
    "        return max(dp[-1][0], dp[-1][1])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
